An anonymous authentication is a technology in which a user (signer), to whom an anonymous authentication certificate with a plurality of attributes and a signature key confirmed thereby are provided by an authentication authority, and who possesses, is able to generate a signature which partially discloses the attributes of the anonymous authentication certificate to a provided text, by using these. From the signature, the disclosed attributes and the fact that the signature is generated by using a signature key based on an anonymous authentication certificate are only become clear.
When the anonymous authentication technology is utilized, for example, if a user has only to disclose a signature to an operator at an online-shop, it is possible to use a service without disclosing important individual information, like a credit card number, to the operator. The operator is not able to know the individual information of the user from the signature. But the operator can provide services to the user with ease and safely recover a service charge through the authentication authority, because the operator is able to know that the user is a member who is authenticated by the authentication authority (e.g. credit card company).
Being sensitive to leakage of individual information, a user intends to reduce the individual information which is disclosed to an operator. Meanwhile, since a cost for management of the individual information increases, an operator intends to reduce the stored individual information on users. Therefore, it is expected that the anonymous authentication technology can provide users and operators with a useful method for using the individual information.
An anonymous authentication signature system described in Non-patent document 1 is explained. FIG. 9 is an explanatory diagram illustrating a configuration of a signature device 500 which is a main element of the system. FIG. 10 is an explanatory diagram illustrating a configuration of a signature verification device 600 which is also a main element thereof.
Suppose that p is a prime number and a randomly-selected element γ of a field (Z/pZ) is an authentication secret key. Public variables includes a natural number N, the prime number p, and character strings describing Group 1, Group 2, Group T, which are with an order p, a bilinear map e from Group 1 and Group 2 to Group T, an isomorphic map π from Group 2 to Group 1, and a Hash function Hash mapping a character string to the field (Z/pZ). The public variable further includes a generator g[2] of Group 2, a generator g[1] of Group 1 where π(g[2])=g[1], and elements h, h[1], . . . , h[N] of Group 2 generated from an output of Hash function. A authentication authority public key y is described as y=g[1]γ.
An attribute of a signer comprises N elements of Z/pZ. Here, attributes of a signer S are denoted as θ[1], . . . , θ[N]. The anonymous authentication certificate and the signature key of the signer are generated by interaction between the signer and the authentication authority through a communication line, and are the anonymous authentication certificate (a, ω) and the signature key ξ which satisfy a relation represented in the formula (1) (aεGroup 2, ωεZ/pZ, ξεZ/pZ).aγ+ω=g[2]hξΠi=1Nh[i]θ[i]  (1)
The signature device 500 shown in FIG. 9 includes a non-interactive zero-knowledge proof generation means 501. A text m to be signed, the authentication authority public key y=g[1]γ, the signature key ξ, the anonymous authentication certificate (a, ω), all the attributes θ[1], . . . , θ[N] which the signer possesses, a group Oε{1, . . . , N} which is information about which attributes are disclosed, and random numbers are inputted into the non-interactive zero-knowledge proof generation means 501 from the outside.
In response to these inputs, the non-interactive zero-knowledge proof generation means 501 generates a non-interactive zero-knowledge proof prf of the knowledge which satisfies the relation shown in the formula (2) with respect to g[1], g[2], h, h[i], θ[i], and y. The prf is a selected attributes disclosure signature (signature).e(yg[1]Ω,A)=e(g[1],g[2]hΞΠiε{1, . . . ,N}h[i]Θ[i]·ΠiεOh[i]θ[i]),(AεGroup2, ΩεZ/pZ, ΞεZ/pZ,{Ξ[i]εZ/pZ}iε{1, . . . ,N})  (2)
The signature verification device 600 shown in FIG. 10 includes a non-interactive zero-knowledge proof verification means 601. The authentication authority public key y=g[1]γ, g[1], g[2], h, h[i] (i=1, . . . , N), disclosed attributes θ[i] (iεO), the text m, and the signature prf are inputted into the non-interactive zero-knowledge proof verification means 601.
In response to these inputs, the non-interactive zero-knowledge proof verification means 601 outputs an “receipt/refusal of receipt” signal indicating whether or not the signature prf which is the non-interactive zero-knowledge proof is a non-interactive zero-knowledge proof of the knowledge which satisfies the relation shown in the formula (3).e(yg[1]Ω,A)=e(g[1],g[2]hΞΠiε{1, . . . , N}h[i]Θ[i]·ΠiεOh[i]θ[i]),(AεGroup2,ΩεZ/pZ,ΞεZ/pZ,{Θ[i]εZ/pZ}iε{1, . . . , N})  (3)
In relation to the technology, the following Patent documents are disclosed. Patent document 1 describes an electronic signature deputizing method which enables a non-user of a key to use the key under conditions the user of the key registered in advance. Patent document 2 describes an anonymous authentication technology where an anonymous public key is made from a proper public key, and authentication is conducted by using the anonymous public key and a proper secret key. Patent document 3 describes a digital signature technology in which load of an authentication authority conducting authentication is reduced by using an attribute certificate, a validity certificate, a time stamp and the like, together with a public key.